1. Field of the invention
This invention relates to law enforcement and more particularly to an automated means for detecting vehicles that have been parked for longer than the legally prescribed period.
2. Background
Municipal governments enact regulations to govern the parking of cars along city streets. Typically, time limits are posted along each street and parking fines are levied on vehicle owners who park their cars for longer than the posted time. Two benefits result from the practice of making and enforcing on-street parking regulations:
1) Traffic congestion is reduced by forcing motorists parked for long periods to find suitable off-street parking arrangements, thereby vacating their more convenient, on-street parking spaces for use by motorists wishing to stop for short periods. PA0 2) The parking fines levied on motorists who violate parking regulations create revenue the municipality. PA0 1) A route is chosen such that all the parked cars along it are subject to the same parking regulation (e.g. 2-hour parking limit). The Officer patrols the route and stops beside every parked car that's encountered. Typically, the patrol is done using a car however foot and bicycle patrols are also common modes of transportation. PA0 2) A temporary mark is made on one of each car's tires using a piece of chalk or similar marking utensil. In order that the officer can attest to having made the mark, some effort is made to keep all the marks similar in size, color, shape and placement. PA0 3) At regular intervals along the route, the time is noted, thereby the enabling a time to be estimated for when each of the chalk-marks was made. PA0 4) After all of the cars parked along the patrol route have been marked, the officer retraces the same route. Care is taken to regulate the speed of the patrol such that the officer returns to the location of each of the chalk-marks just after the permissible parking period has expired (e.g. if the posted time limit is two hours, then the officer must return to the same location slightly more than two hours after chalk marks were made at that location). PA0 5) During the second trip over the patrol route, the officer visually inspects the tires of each and every vehicle looking for a chalk-mark made during the previous circuit. A found chalk-mark serves as evidence that the marked vehicle has not moved during the period the Officer has been away patrolling the rest of the circuit. PA0 6) When a chalk-marked car (i.e. an illegally parked car) is sighted the officer issues it a parking citation. After writing the details of the infraction onto the citation and attaching it to the offending vehicle, the Officer continues along the route, slowing down or speeding up as necessary to stay on-schedule for detecting subsequent parking violations.
In order to reap these benefits, the fundamental technical problem faced by Parking Authorities is how to detect when vehicles are in violation of the posted time limit. Heretofore, two violation-detection and enforcement technologies have been employed:
1) Parking meters PA1 2) Timed chalk-marking of car tires PA1 Vectorizing the raster image (hereafter referred to as creating the "vector-model") PA1 Step 1)Isolating only those vectors that describe the license plate within the vector-model (hereafter referred to as creating the "plate-model") PA1 Step 2)Recognizing the alphanumeric characters in the plate-model (hereafter referred to as creating the "plate-string")
Enforcement Using Parking Meters
Parking meters are timing devices installed adjacent to each parking space that the Parking Authority wishes to enforce. Once installed, parking meters permit motorists to rent each on-street parking space for short periods. To rent the space, the motorist must insert coins into the meter, thereby starting a timer mechanism that suppresses display of an "Illegally Parked" flag. When the purchased parking period has expired, the "Illegally Parked" flag is again made plainly visible, thereby enabling a Parking Enforcement Officer patrolling the area to see at a glance that the parking space is illegally occupied. The officer continually inspects every parking meter along the patrol route and issues citations to those cars that are illegally parked.
Detecting parking violations with parking meters is an effective means of enforcing regulations, particularly in areas with high traffic density such as downtown commercial districts. A significant advantage of using parking meters to detect infractions is that they also provide a means for collecting a "pay per use" rental fee. The requirement to insert coins provides a continual stream of revenue to the municipality, even if no vehicle is ever cited for an over-parking infraction. However, each parking space requires its own parking meter, which is an expensive piece of equipment to purchase and install. The capital costs of initiating a parking metered enforcement program are considerable. Since the Enforcement Officer must visually inspect each parking meter along the route, patrolling the meters is a tedious, labour intensive activity that adds to the overall cost of metered enforcement. In congested, downtown areas, officers are often obliged to patrol the route on foot, thereby adding to the labor cost of the system. Maintaining the meters in good working order and emptying their contents is another significant expense related to metered enforcement.
Enforcement Using Timed Chalk-Marking of Car Tires
The high cost of installing, maintaining and patrolling parking meters limits their cost-effectiveness in many on-street parking situations. In particular, low-density areas outside the downtown core may be considered "not profitable enough" to warrant the use of parking meters. In these areas, the other method of parking enforcement commonly employed is "timed chalk-marking of car tires" (hereafter referred to as "tire-chalking").
Parking regulation enforcement using the tire-chalking methodology is as follows:
The chalk-mark method of detecting parking violations is commonly used along lightly traveled streets where metered enforcement would not be cost-effective. Since no capital investment in parking meters is required to provide infrastructure, a tire-chalking enforcement program is less costly to initiate than an enforcement program based on parking meters.
Furthermore, tire-chalking provides a more flexible means of parking enforcement. Patrol routes can be quickly adapted to suit the changing parking habits that generally occur at different times of the day, on different days of the week or in different seasons of the year; something that meters cannot easily accommodate.
While the capital cost of using chalk-marks as a means to enforce parking regulations is less than that of using parking meters, the labor cost of using chalk-mark detection is significantly higher. The principal factor contributing to the workload is the need to manually mark every car along the patrol route . . . a task that is both physically demanding and time consuming.
Furthermore, the route must be patrolled twice before any infractions can be detected whereas parking meters guide the Officer to infractions every time the route is patrolled. The high labour cost of first applying chalk-marks and then searching for them significantly reduces this methodology's attractiveness as a parking enforcement means. Furthermore, the second traverse of the patrol route is often dedicated only to inspecting tires and issuing citations, thereby permitting newly parked vehicles to go unmarked.
Furthermore, detection and prosecution is based entirely on the presence of chalk-marks on each vehicle. Vehicle owners can evade prosecution simply by hiding the mark. Typically, each tire is marked on its tread surface so simply moving the car a few feet within the parking space will rotate it away from the officer's view, thereby making it impossible to detect the infraction during the second traverse of the patrol route. If the chalk-mark has been made on the side of the tire rather than on its tread, the mark can still be easily rubbed off to evade detection.
Regardless of whether parking regulations are enforced using parking meters or tire-chalking, once a parking infraction is detected, creating a legal citation and serving it on the vehicle's owner takes a considerable amount of time and effort. The main factor contributing to this workload is the requirement for the officer to write down all the details of the infraction by hand onto a paper citation form before affixing it to the offending vehicle (time, location, license plate number, nature of infraction etc). Furthermore, the labour cost of processing each parking citation is increased by the requirement to transcribe the hand-written data into a computerized system that tracks the infraction through the court system.
Another factor that degrades the performance of both enforcement systems is their incapacity to detect "scofflaw" motorists. "Scofflaw" is the term commonly used by Parking Authorities for a motorist who flouts parking regulations. Scofflaws flout parking regulations by discarding or otherwise ignoring all parking citations they receive. Neither the parking meter enforcement methodology nor the tire-chalking enforcement methodologies can detect whether or not the vehicle's owner is likely to pay the fine levied for the infraction. Since many of the citations written by officers are ignored by scofflaw motorists, the inability of both the meter and chalk-mark enforcement methodologies to deal effectively with scofflaw motorists reduces their fiscal efficiency.
It is therefore the purpose of the present invention to provide a means of enforcing parking regulations that eliminates the drawbacks inherent to using either parking meters or tire-chalking.
LPR Technical Background
The present invention exploits "Optical Character Recognition". OCR image analysis is a well-established technology that has many applications in the publishing and archiving industry. Essentially, OCR is an image analysis process that converts a raster-scanned image of printed characters into machine readable ASCII codes, thereby eliminating the need to re-type old documents into a computer and rendering them amenable to automated processing.
One common application of OCR technology is to digitize a vehicle's license plate number from its raster image. When applied to vehicular imagery, OCR technology is commonly referred to as "License Plate Recognition" (LPR). Heretofore, LPR has been applied to stationary law enforcement and security applications (e.g. identifying vehicles in controlled areas such as parking garages). LPR technology has also been successfully applied in revenue collection applications (e.g. automatic billing of motorists using toll highways).
LPR is a complex process that is well documented in the literature and prior art. Various aspects of LPR methodology and terminology are relevant to the present invention and therefore merit summary description.
Essentially, LPR is comprised of three operations that are sequentially applied to the vehicle's raster image. These processes attempt to progressively refine the complex, unique identification of the vehicle captured in the raster image into an alphanumeric string of text identical to the text inscribed on the vehicle's license plate. Since this alphanumeric string of text is compact, easily comprehended and legally linked to the vehicle's owner, its correct extraction from the raster image is the ultimate goal of LPR. The interim digital encapsulations of the raster image that are part of the LPR process are less desirable however they also uniquely identify the vehicle in a way that has been exploited in certain LPR applications. The interim encapsulations of LPR are analogous to a person's fingerprint while the end product of LPR (the license plate number) is analogous to the same person's name.
The three conceptual steps that comprise LPR are:
The three steps that comprise LPR can be summarized as follows:
Step 1) Vectorizing The Raster Image:
Discrete physical objects depicted in a raster image will generate zones within which all the pixels share similar color or gray-scale values. Vectors are mathematically defined lines that trace the perimeter of these zones. Some LPR algorithms make use of the aggregation of pixels inside these zones rather than their perimeter however for the purpose of this summary, they can be considered the same geometric entities. Before tracing the outline of these zones, spatial filtering algorithms are applied to the raster image to compensate for the effects of extraneous pixel noise (such as varying color caused by precipitation, dirt on the vehicle, slight variations in paint color, etc). The objective of vectorization is to identify and group only those pixels that correspond to real physical objects portrayed as discrete visual features in the raster image. In the case of a parked car's raster image, the desired vectors follow the silhouettes of the various mechanical parts and visual features that comprise the car (windows, fenders, bumpers, license plate, license plate text, dirt on license plate, etc). The vectorization algorithm may also outline discrete elements in the visible background scenery (sidewalk, trees, pedestrians etc.).
Spurious shadows in the vehicle's raster image will degrade the spat ial fidelity of vectors extracted from it. Therefore, many LPR systems improve their performance by illuminating the scene with supplementary lights, to minimize shadow effects in the image presented to the vectorization algorithm.
The set of all vectors extracted from a raster image using a particular algorithm constitutes a unique "digital fingerprint" for the scene in the ima ge. This unique identifier is hereafter referred to as the image's "vector-model". A vector-model generally occupies less storage space than the raster image from which it is derived. In addition, since the points and lines in the vector-model are mathematically defined entities, they lend themselves to the rapid computations required in steps 2 and 3 described below.
Step 2) Recognizing the License Plate Within the Vector-Model:
Algorithms are then applied to the image's vector-model to isolate only those vectors or zones of similar pixels that describe the license plate's physical structure. This unique "digital fingerprint" of the license plate is hereafter referred to as the "plate-model". Different algorithms could be applied to the vector-model to try to isolate other physical structures (the "bumper-model" the "window-model" etc). However, for typical applications, the license plate is the physical object of greatest interest, therefore the plate-model is the subset searched for within the image.
The rectangular shape of a license plate provides one criterion for testing if a candidate subset set of vectors is indeed the plate-model. However, there will typically be many vectorized rectangles in the vector-model that complicate isolating the plate-model (dealer logos, bumper stickers, parking permits, decorative trim etc.). Therefore, multiple geometric and stochastic tests are typically made on all candidate plate-models in order to rank their probability of being the correct one. When one of the candidate plate-models achieves a sufficiently high probability of modeling the real license plate, it is passed on to step 3 (described below).
Some LPR implementations only vectorize a subset of the total raster image and create the plate-model directly. Various methods have been used to directly localize the plate. One approach is to exploit the reflective paint used on many license plates. The plate's reflective surface can be used to localize it within the image without the need to vectorize other physical elements in the scene. Different LPR manufacturers use different terminology for the image's interim states as it is prepared for recognition of the license plate's alphanumeric characters. For the purposes of the present invention, the end product of LPR (the license plate number) as well as its precursor stages (referred to here as the raster image, the vector-model and the plate-model) are all encompassed within the term "unique vehicle identifier".
Step 3) Recognizing the Alphanumeric Characters in the Plate-Model:
The plate-model is then analyzed to transform the vectorized zones within its perimeter into an alphanumeric string of characters that spell out the vehicle's license plate number. The recognized string of text that estimates the vehicle's license plate number is hereafter referred to as the "plate-string".
Typically, before attempting to recognize the plate-string's characters, the distortion caused by an oblique camera angle is geometrically rectified. This geometric rectification procedure is generally referred to as "de-skewing". Since character recognition is based on analysis of the plate-model's geometry, de-skewing the perspective distortion of the vectorized zones will improve the accuracy of the character recognition algorithm.
Typically, one of three OCR methodologies is used to recognize each character of the plate-string from within the plate-model. "Structural analysis", "pattern matching", and "neural networks" are the terms commonly used for these algorithms. Each of these complex algorithms is well documented in the literature and has its unique advantages and disadvantages. Some LPR systems use combinations thereof to improve the reliability of the characters recognized from the plate-model.
To improve the reliability of character recognition, the LPR algorithm must also be customized to accommodate the different fonts, color schemes and character syntax's appearing on the plates issued in different transportation jurisdictions.
Full Recognition Mode LPR
The sequential 3-step algorithm described above is commonly known as "Full Recognition Mode LPR". Full Recognition Mode LPR algorithms cannot recognize the plate-strings of all observed vehicles with 100 percent accuracy. However, for some applications a certain number of plate-string errors is acceptable. For example, it is acceptable that a certain percentage of vehicles passing through a toll plaza not be correctly recognized (and thereby escape being billed the toll charge). Unrecognizable plates can be tolerated if the algorithm is at least able to compute that its best estimate of the plate-string is not sufficiently reliable, thereby permitting the enforcement system to simply ignore those "difficult" plate readings.
Pattern-Matching LPR
Some other LPR applications demand a very high degree of certainty that certain vehicles will be recognized. For example, a security camera might be setup to control access to a parking garage. In this scenario, it may be imperative that only authorized vehicles are permitted to enter and furthermore, that those vehicles are always allowed to pass. To deal with this requirement an algorithmic subset of Full Recognition Mode LPR known as "Pattern-matching LPR" is commonly employed.
"Pattern-matching LPR" doesn't rely on complete recognition of the alphanumeric plate-string to identify a vehicle. Instead, Pattern-matching LPR stops short of estimating the plate-model and simply compares (matches) the two vector-models (patterns) that are derived from two captured raster images. If the mathematical correlation between the two vector-models is sufficiently high then the algorithm concludes that the two images depict the same vehicle.
In the access control example given above, the vector model's of all authorized vehicles would be captured a priori and stored in the system's database, thereby permitting the Pattern-Matching algorithm to refer to the known vector-model of all authorized vehicles that request entry to the garage. The vector-models of all unauthorized vehicles will not correlate to any of the authorized vector-models and can therefore be denied access to the garage.
Conceptually, Pattern-matching LPR is the same as performing Full Recognition Mode LPR on the two raster images and then correlating the two computed plate-strings to see if they contain the same text (pattern). However, Pattern-Matching LPR has one important advantage over Full Recognition Mode LPR; since a plate-model contains more mathematically defined spatial information about the vehicle than a fully recognized plate-string, the correlation computed between two vector-models is less vulnerable to vectorization errors than the correlation of two fully recognized plate-strings. Pattern-matching LPR is therefore more reliable at determining if two raster images portray the same vehicle. However, Pattern-matching LPR cannot extract useful information from a single image and cannot make the legal link to the vehicle's owner (only Full Recognition Mode LPR can provide that information).